//518.零钱兑换II
//https://leetcode.cn/problems/coin-change-ii/?envType=daily-question&envId=2024-03-25
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        dp[0] = 1; //组成为0的方法只有一种 什么的不选

        //依次枚举每元是否需要该比该元小的元组成
        //一旦该元的更小元变化 后面也会变化
        //例如3元变化了 那么五元的组成为2+3 此时五元的组成也会发生变化
        //所以较小的数字变化需要更新较大的数字
        //当硬币中有 面值=coins 中的硬币时 需要选取 面值-coins=0 所以dp[0]=1
        for(int m:coins)
            for(int i = m;i<=amount;++i)
                //一定会有i>=amount
                //所以i除了更新自己以外 还需要更新比自己大的 组成需要i元的数量
                dp[i] += dp[i-m];

        return dp[amount];
    }
};